home *** CD-ROM | disk | FTP | other *** search
/ MacTech 1 to 12 / MacTech-vol-1-12.toast / Source / MacTech® Magazine / Volume 08 - 1992 / 08.07 Nov⁄Dec 92 / Programmers' Challenge / count-paths.c next >
Encoding:
C/C++ Source or Header  |  1992-10-04  |  12.9 KB  |  416 lines  |  [TEXT/KAHL]
  1. #if 0
  2. Item    2756811                         2-Sept-92        15:57
  3.  
  4. From:   GALWAY@JENSEN.CS.UTAH.EDU@INTERNET# 
  5.  
  6. To:     WHITEPALM                       White Palm, Mike Scanlin,CST
  7.  
  8. INTERNET# Document Id: <9209022257.AA18389@jensen.cs.utah.edu>
  9.  
  10. ------------------------------------------------------------------------------
  11.  
  12. Sub:    count-paths.h, count-paths.c
  13.  
  14. From: galway@jensen.cs.utah.edu
  15. To: AppleLink.Apple.COM!WHITEPALM@cs.utah.edu
  16.  
  17. #endif
  18.  
  19. /*  count-paths.c
  20.  *
  21.  *    Copyright (C) 1992,  William F. Galway
  22.  *
  23.  *    Anyone can do what they like with this code, as long as they
  24.  *    acknowledge its author, and include this message in their code.
  25.  */
  26.  
  27. /*
  28.  * This program solves the September 1992 Mac Tutor Challenge problem,
  29.  * the statement of which follows.  (Presented by Mike Scanlin.)
  30.  *
  31.  *----------------------------------------------------------------------
  32.  *
  33.  * How Many Ways Can You Spell "CAT"?
  34.  *
  35.  * Given an order N (from 2 to 10) of a graph matrix and a character value for
  36.  * each node in the graph, calculate the number of unique paths that correctly
  37.  * spell out a given word (starting from any node). For instance, if N is 3 and
  38.  * the nodes are C, T, C, A, R, A, T, A and C, your input graph looks
  39.  * like this:
  40.  *
  41.  *  C---T---C
  42.  *  |   |   |
  43.  *  A---R---A
  44.  *  |   |   |
  45.  *  T---A---C
  46.  *
  47.  *
  48.  * Given an input word, say "CAT", you start at each of the 9 nodes and
  49.  * see how many unique paths there are that spell out "CAT". In this
  50.  * example, there are two solutions: (1,1), (2,1), (3,1) and (3,3),
  51.  * (3,2), (3,1). If the input word is "CAR", then there are four
  52.  * solutions: (1,1), (2,1), (2,2) and (1,3), (2,3), (2,2) and (3,3),
  53.  * (2,3), (2,2) and (3,3), (3,2), (2,2). For the input word "CATARACT"
  54.  * there are eight solutions.
  55.  *
  56.  * Each path may cross any node any number of times but you cannot go
  57.  * diagonally from node to node nor can you use the same node twice in a
  58.  * row (in the event that there are two letters next to each other in the
  59.  * input word that are the same). Don't worry about case sensitivity
  60.  * (assume everything is upper or lower case). The input word length is
  61.  * from 1 to 255 (a PString).
  62.  *
  63.  *----------------------------------------------------------------------
  64.  *
  65.  * The algorithm used by this implementation avoids "combinatorial
  66.  * blowup" by working backwards through the input word, keeping a
  67.  * "count table" showing the number of paths for the substring at each
  68.  * node.  For example, for the string "CAR" we would get the
  69.  * following counts (count tables) at each stage:
  70.  *  -for "r":
  71.  *     0  0  0
  72.  *     0  1  0
  73.  *     0  0  0
  74.  *  -for "ar":
  75.  *     0  0  0
  76.  *     1  0  1
  77.  *     0  1  0
  78.  *  -for "car":
  79.  *     1  0  1
  80.  *     0  0  0
  81.  *     0  0  2
  82.  * giving a total of 4 solutions found at the final stage.
  83.  * (This non-recursive approach is reminiscent of the iterative versus
  84.  * the recursive method of computing Fibonacci numbers.)
  85.  *
  86.  * We actually keep two count tables around, one giving counts for the
  87.  * "previous stage" (the "previous table"), and one being built up for
  88.  * the "current stage" (the "current table").  We build the current
  89.  * table by locating occurrences of the leading character of the
  90.  * substring, and then summing the counts from the four neighboring
  91.  * locations in the previous table.  To ease the problem of dealing
  92.  * with the edges of the tables, we allocate "dummy" rows and columns
  93.  * at the edges of our count tables.  The counts at the edges always
  94.  * remain zero, while the interesting stuff goes on in the interior of
  95.  * the tables.
  96.  *
  97.  * To simplify (and speed up) the task of locating occurrences of
  98.  * characters in the matrix, we first build an "index" for the matrix
  99.  * which is basically a linked list of pointers and then index into
  100.  * the index (!) by the character that we need the location(s) of.
  101.  * The index needs building only once for a given matrix, after which
  102.  * the count_paths routine may be called (see how CountPaths invokes
  103.  * count_paths below).
  104.  *
  105.  * Other points to note:
  106.  *
  107.  *  -- Use of "Native" pointers for less "pointer arithmetic".
  108.  *  -- The result returned by CountPaths is more properly
  109.  *     interpreted as an unsigned long rather than as a signed long.
  110.  *  -- These routines are not robust when called with matrices
  111.  *     of order outside the range 1..MAXORDER.
  112.  */
  113.  
  114. #include "count-paths.h"
  115. #include <stdio.h>
  116.  
  117. #if DEBUG
  118. /* Return TRUE/FALSE depending on whether index is consistent with */
  119. /* matrix of given order.  Trys to find "all problems", not just */
  120. /* the first.  */
  121. BOOL CheckIndex(BOOL verbose, long order, const char *matrix,
  122.                 const Index *index)
  123. {
  124.     unsigned char *chrp;
  125.     unsigned long ch;
  126.     LocNode *spot;
  127.     long offset,i,j;
  128.     long delta_y = index->dy;
  129.     long match_count = 0;
  130.     BOOL result = TRUE;
  131.  
  132.     if (delta_y != order+2) {
  133.         if (verbose) {
  134.             printf("Delta-y in index = %ld != %ld = order+2\n",
  135.                    delta_y, order+2);
  136.         }
  137.         result = FALSE;
  138.     }
  139.  
  140.     for (ch=0; ch<=255; ch++) {
  141.         for (spot=(index->char_index)[ch].next;
  142.              spot!=NULL;
  143.              spot=spot->next) {
  144.             offset = spot - index->index_matrix;
  145.             i = offset/delta_y - 1;
  146.             j = offset%delta_y - 1;
  147.             if (i<0 || i >= order || j<0 || j>=order) {
  148.                 if (verbose) {
  149.                     printf("Index points to bad location (%ld,%ld)"
  150.                            " in %ld by %ld matrix\n",
  151.                            i,j,order,order);
  152.                 }
  153.  
  154.                 result = FALSE;
  155.             } else {
  156.  
  157.                 chrp = (unsigned char *)(matrix + order*i + j);
  158.                 if (*chrp != ch) {
  159.                     if (verbose) {
  160.                         printf("Index says character '%c' at (%ld,%ld)"
  161.                                " should be '%c'\n",
  162.                                *chrp, i,j, (char)ch);
  163.                     }
  164.  
  165.  
  166.                     result = FALSE;
  167.                 } else {
  168.                     match_count++;
  169.                 }
  170.             }
  171.         }
  172.     }
  173.  
  174.     if (match_count != order*order) {
  175.         if (verbose) {
  176.             printf("Total of %ld index matches found,"
  177.                    " should have been %ld=%ld*%ld\n",
  178.                    match_count, order*order, order, order);
  179.         }
  180.  
  181.         result = FALSE;
  182.     }
  183.  
  184.     return result;
  185. }
  186.  
  187. BOOL CheckZeroed(BOOL verbose, long tblsize, const long *table)
  188. {
  189.     const long *tblp;
  190.     BOOL result = TRUE;
  191.  
  192.     for (tblp=table; tblp<table+tblsize;tblp++) {
  193.         if (*tblp != 0) {
  194.             result = FALSE;
  195.             if (verbose) {
  196.                 printf("Non-zero count in table[%ld]=%lu\n",
  197.                        tblp-table, *tblp);
  198.             }
  199.         }
  200.     }
  201.  
  202.     return result;
  203. }
  204. #endif
  205.  
  206. #if VERBOSE
  207. void print_counts(const Index *index, const long *count_table)
  208. {
  209.     long order = index->dy-2;
  210.     long i,j;
  211.     const long *countp;
  212.  
  213.     /* Start just past first row.  */
  214.     countp = count_table+order+2;
  215.     i = order-1;
  216.     do {
  217.         /* Skip first column of row.  */
  218.         countp++;
  219.         j = order-1;
  220.         do {
  221.             printf("  %lu", *countp++);
  222.         } while (j--);
  223.         /* Skip last column of row.  */
  224.         countp++;
  225.         printf("\n");
  226.     } while (i--);
  227.  
  228.     return;
  229. }
  230. #endif
  231.  
  232. /* Build up index for matrix of given order.  */
  233. void BuildIndex(long order, const char *matrix, Index *index)
  234. {
  235.     register unsigned char *chrp;
  236.     register LocNode *spot, *spot2;
  237.     long i,j;
  238.  
  239.     /* Zero out the char_index (256 entries).  */
  240.     spot = index->char_index;
  241.     spot2 = spot+256;
  242.     do {
  243.         (spot++)->next = NULL;
  244.     } while (spot < spot2);
  245.  
  246.     /* Build up the index... The c'th entry in char_index points to */
  247.     /* a chain of pointers residing in index_matrix...  Note that */
  248.     /* "edge" rows and columns are allowed to contain nonsense.  */
  249.     spot = index->index_matrix+order+3;
  250.     chrp = (unsigned char *)matrix;
  251.     i = order;
  252.     do {
  253.         j = order;
  254.         do {
  255.             /* char_index[char] points to head of chain for char.  */
  256.             /* Set spot pointed at to point to "next" spot with ch in it */
  257.             /* (as previously stored in char_index).  */
  258.             spot2 = &index->char_index[*chrp++];
  259.             spot->next = spot2->next;
  260.             spot2->next = spot++;
  261.         } while (--j);
  262.         /* Skip last & first columns of row.  */
  263.         spot += 2;
  264.     } while (--i);
  265.  
  266.  
  267.     index->dy = order+2;
  268.  
  269. #if DEBUG
  270.     if (!CheckIndex(TRUE, order, matrix, index)) {
  271.         printf("****CheckIndex failed.****\n");
  272.     }
  273. #endif
  274.  
  275.     return;
  276. }
  277.  
  278. /* Count paths using previously built index.  */
  279. long count_paths(const Index *index, const StringPtr word)
  280. {
  281.     register unsigned char *chrp;
  282.     register long dyoffset;
  283.     /* tbl_offset gives offset from "current counts" table to */
  284.     /* "previous counts" table.  I.e., */
  285.     /* previous_counts = current_counts+tbl_offset.  */
  286.     long tbl_offset;
  287.     /* current_offset, previous_offset give offset from index->index_matrix */
  288.     /* to current/previous count tables.  */
  289.     register long current_offset;
  290.     register long previous_offset;
  291.     LocNode *spot;
  292.     long *countp;
  293.     register long total;
  294.     long count_tables[2*(2+MAXORDER)*(2+MAXORDER)];
  295.  
  296.     /* Point chrp to last char of word.  */
  297.     chrp = word + *word;
  298.  
  299.     /* Initialize misc offsets, pointers.  */
  300.     dyoffset = index->dy*sizeof(long);
  301.     /* (short) avoids subroutine call for multiply for some systems.  */
  302.     tbl_offset = (short)(index->dy)*(short)dyoffset;
  303.     current_offset = (Native *)count_tables-(Native *)(index->index_matrix);
  304.     previous_offset = tbl_offset+current_offset;
  305.  
  306.     /* Zero out the count tables.  */
  307.     countp=count_tables;
  308.     do {
  309.         *countp++ = 0;
  310.     } while (countp < (long *)((Native *)count_tables+2*tbl_offset));
  311.  
  312. #if DEBUG
  313.     /* Verify that tables were zeroed. */
  314.     if (!CheckZeroed(TRUE, 2*(index->dy)*(index->dy), count_tables)) {
  315.         printf("****CheckZeroed failed.****\n");
  316.     }
  317. #endif
  318.  
  319.     total = 0;
  320.  
  321.     /* Initialize counts for "previous table".  (It will soon be previous!)  */
  322.     for (spot=(index->char_index)[*chrp].next; spot!=NULL; spot=spot->next) {
  323.         *(long *)((Native *)spot+previous_offset) = 1;
  324.         total++;
  325.     }
  326.  
  327. #if VERBOSE
  328.         /* We depend on word being null (0 byte) terminated here.  */
  329.         printf("Counts for %s are:\n", chrp);
  330.         print_counts(index,
  331.                      (long *)((Native *)(index->index_matrix)
  332.                               +previous_offset));
  333. #endif
  334.  
  335.     if (total==0 || --chrp<=word) {
  336.         return total;
  337.     }
  338.  
  339.     while (TRUE) {
  340.         total = 0;
  341.         for (spot=(index->char_index)[*chrp].next;
  342.              spot!=NULL;
  343.              spot=spot->next) {
  344.             countp = (long *)((Native *)spot + previous_offset);
  345.             /* Hairy expression avoids variable, may free up register...  */
  346.             total += *(long *)((Native *)spot + current_offset)
  347.                   = *(countp-1)
  348.                   + *(countp+1)
  349.                   + *(long *)((Native *)countp-dyoffset)
  350.                   + *(long *)((Native *)countp+dyoffset);
  351.         }
  352. #if VERBOSE
  353.         /* We depend on word being null (0 byte) terminated here.  */
  354.         printf("Counts for %s are:\n", chrp);
  355.         print_counts(index,
  356.                      (long *)((Native *)(index->index_matrix)
  357.                               +current_offset));
  358. #endif
  359.         if (total==0 || --chrp<=word) {
  360.             return total;
  361.         }
  362.  
  363.       /* Swap "current" and "previous" count tables.  */
  364.         current_offset += tbl_offset;
  365.         previous_offset -= tbl_offset;
  366.         tbl_offset = - tbl_offset;
  367.  
  368.         /* Zero out current counts, only need touch non-zero entries.  */
  369.         for (spot=(index->char_index)[*(chrp+2)].next;
  370.              spot!=NULL;
  371.              spot=spot->next) {
  372.             *(long *)((Native *)spot + current_offset) = 0;
  373.         }
  374. #if DEBUG
  375.         /* Verify that current counts were zeroed. */
  376.         if (!CheckZeroed(TRUE,
  377.                          (index->dy)*(index->dy),
  378.                          (long *)((Native *)(index->index_matrix)
  379.                                   +current_offset))
  380.             ) {
  381.             printf("****CheckZeroed failed.****\n");
  382.     }
  383. #endif
  384.  
  385.     }
  386. }
  387.  
  388. long CountPaths(short order, char *matrix, const StringPtr inputWordPtr)
  389. {
  390.     long ord=order;
  391.     Index index;
  392.  
  393.     /* Problem statement restricts word length to be >0, but be */
  394.     /* paranoid since count_paths(...) is not robust for 0 length */
  395.     /* words.  Return 0 if empty (zero length) word.  */
  396.     if (*inputWordPtr == 0) {
  397.         return 0;
  398.     } else if (*inputWordPtr == 1) {
  399.         /* Avoid work of building index, etc. for length one words.  */
  400.         register char ch=(char)inputWordPtr[1];
  401.         char *chrp = matrix;
  402.         long total=0;
  403.  
  404.         do {
  405.             if (ch == *chrp++) {
  406.                 total++;
  407.             }
  408.         } while (chrp < matrix+order*order);
  409.         return total;
  410.     } else {
  411.         /* Invoke count_paths after building the index...  */
  412.         BuildIndex(ord, matrix, &index);
  413.         return count_paths(&index, inputWordPtr);
  414.     }
  415. }
  416.